package com.banmoon.datastructure.ThreadBinaryTree;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.Objects;

/**
 * 线索二叉树
 */
@Data
@NoArgsConstructor
@AllArgsConstructor
public class ThreadBinaryTree {

    /**
     * 根节点
     */
    private ThreadTreeNode root;

    /**
     * 临时存储前驱节点
     */
    private ThreadTreeNode preNode = null;

    public ThreadBinaryTree(Integer value) {
        this.root = new ThreadTreeNode(value);
    }

    /**
     * 线索化
     */
    public void thread() {
        thread(root);
    }

    /**
     * 线索化
     */
    public void thread(ThreadTreeNode node) {
        if (Objects.isNull(node))
            return;
        // 线索化左节点
        thread(node.leftNode);
        // 处理当前节点的前驱节点
        if (node.leftNode == null) {
            node.leftNode = preNode;
            node.leftNodeType = 1;
        }
        // 处理前驱节点的后继节点
        if (Objects.nonNull(preNode) && Objects.isNull(preNode.rightNode)) {
            preNode.rightNode = node;
            preNode.rightNodeType = 1;
        }
        preNode = node;
        // 序列化右节点
        thread(node.rightNode);
    }

    /**
     * 遍历
     */
    public void show() {
        ThreadTreeNode tempNode = root;
        while (Objects.nonNull(tempNode)) {
            // 循环找到中序遍历最开始的节点
            while (tempNode.leftNodeType == 0)
                tempNode = tempNode.leftNode;
            // 打印当前的节点
            System.out.print(tempNode.value);
            // 找到后继节点
            while (tempNode.rightNodeType==1) {
                tempNode = tempNode.rightNode;
                System.out.print(tempNode.value);
            }
            // 知道没有找到后继节点后，替换临时节点，重新进行遍历
            tempNode = tempNode.rightNode;
        }
    }

    @Data
    @NoArgsConstructor
    public static class ThreadTreeNode {

        /**
         * 节点值
         */
        private Integer value;

        /**
         * 左节点
         */
        private ThreadTreeNode leftNode;

        /**
         * 右节点
         */
        private ThreadTreeNode rightNode;

        /**
         * 左节点类型，0=子节点，1=前驱节点
         */
        private short leftNodeType;

        /**
         * 左节点类型，0=子节点，1=后继节点
         */
        private short rightNodeType;

        public ThreadTreeNode(Integer value) {
            this.value = value;
        }
    }
}
